/**
 * Copyright (c) 2010 Claudio Imbrenda.
 * This program is released under the terms of the GNU GPL License, version 3 or later.
 */
 
#include <stdlib.h>
#include <stdio.h>

#include "visit.h"

int visits = 0;
int bestvisit = 0;
int maxvisits=10;

/** Performs a Breadth-First visit. Simple implementation.
 @param g the graph.
 @param res the array of size g->size that will contain the minimum distances
  from the starting node. If NULL, minimum distances will not be stored.
 @param fns number of starting nodes.
 @param firstnodes the array with the starting nodes. Must be fns elements
  long.
 @param marks bit array to store node markings. If NULL, node markings will
  not be stored.
 @param tree uint array to store the visit tree. If NULL, the visit tree will
  not be stored.
 @param vres a pointer to a visit_result struct to store visit details to. If
  NULL, visit details will not be stores.
 @param in_tree a previous visit tree. The visit will be performed only on the
  tree. If NULL, the visit will be performed on the whole graph.
 @return the last element inserted in the queue.
*/
uint visit(struct tngraph*g, int* res, uint fns, const uint *firstnodes, uchar*marks, uint*tree, struct visit_result * vres, const uint*in_tree){
 uint cx;
 uint head=0,tail=0;
 uint*q = malloc(g->size * sizeof(uint)); /* the queue */
 uint fin=firstnodes[0];
 int res_flag=0;
 
 /* we abort if we do more visits that allowed */
 if((maxvisits>=0)&&(visits>=maxvisits)){fflush(stdout);abort();}

 if(res==NULL){
  res=malloc(g->size * sizeof(int));
  res_flag=1;
 }
 
 if(vres!=NULL){
  vres->visited_nodes=0;  
 }

 
 for(cx=0;cx<g->size;cx++) res[cx]=-1;
 if(tree!=NULL)for(cx=0;cx<g->size;cx++) tree[cx]=cx;


 /* put the first nodes in the queue */
 for(cx=0;cx<fns;cx++){
  res[firstnodes[cx]]=0;
  if(marks!=NULL)MARKNODE(firstnodes[cx],marks);
  if(vres!=NULL)vres->visited_nodes++;
  q[head++]=firstnodes[cx];
 }
 
 /* while the queue is not empty..*/
 while(head>tail){
   uint cur = q[tail++]; /* dequeue the first node */
   int dep = res[cur]+1; /* update the depth */
   
   /* if this is the last node of the queue, we remember the node */
   if(head==tail)fin=cur; 
   
   uint nc;
   uint* nei;
   
   /* get the neighbours of the current node */
   GETNEIGHBOURS(g, cur, nei, nc);
  
   /* for each unvisited neighbour, we enqueue it */
   for(cx=0;cx<nc;cx++){
     uint t = nei[cx];
     /* limit the visit to the given tree, if needed */
     if( ((in_tree==NULL)?1:((in_tree[t]==cur)||(in_tree[cur]==t))) && (res[t]<0)){
       res[t]=dep; /* update the depth of the enqueued node */
       q[head++]=t; /* put the node in the queue*/
       if(marks!=NULL)MARKNODE(t,marks); /* mark the node (if needed) */
       if(vres!=NULL)vres->visited_nodes++; /* increment the counter of visited nodes */
       if(tree!=NULL)tree[t]=cur; /* build the visit tree (if needed) */
     }
   }
 }
 
 if(vres!=NULL){
  vres->last_node=fin;
  vres->eccentricity=res[fin];
 }

 /* increment the global counter of visits performed  */
 visits++; 
 free(q);
 if(res_flag)free(res);
 return fin;
}


/** Returns the index of the highest value in the array.
 @param s size of the array
 @param a the array
*/
uint highestindex(uint s, int*a){
 uint res=0;
 uint cx;
 
 for(cx=0;cx<s;cx++)
   if(a[cx]>a[res])
     res=cx;
   
 return res;
}

/** Returns the index of the highest value in the array, provided the 
 corresponding node is not marked.
 @param g the graph
 @param a the array
*/
uint highestnonvisitedindex(uint s, int*a, unsigned char*marks){
 uint res=0;
 uint cx;
 
 for(cx=0;cx<s;cx++)
   if((a[cx]>a[res])&&!(ISMARKED(cx,marks)))
     res=cx;
   
 return res;
}


/** Returns the highest value in the array.
 @param s size of the array
 @param a the array
*/
int arraymax(uint size, int*array){
 int res=array[0];
 int cx;
 
 for(cx=1;cx<size;cx++)
  if(array[cx]>res)res=array[cx];

 return res;
}


/** Finds the giant component in the graph, and removes the other nodes.
 @param g the graph
*/
void findgigantandkill(struct tngraph*g){
 uint cx,n,c;
 int*res = malloc(g->size*sizeof(int));
 uchar*marks;
 int nodesleft = g->size;
 uint bestnode=-1;
 int bestsize=0;
 
 marks=MALLOCMARKS(g->size);
 
 /* kill all the isolated nodes */
 for(cx=0;cx<g->size;cx++)
   if(g->nodes[cx].size==0){
    MARKNODE(cx,marks);
    nodesleft--;
   }
 
 /* get a random unmarked node and perform a visit.. */
 do{
  c=0;
  n = getrandomunmarkednode(g,marks);
  fprintf(ERR,"trying: %d (nodesleft: %d)..",n,nodesleft);
  fprintf(ERR,".");
  visit(g,res,1,&n,NULL,NULL,NULL,NULL);visits=0;
  fprintf(ERR,".");
  for(cx=0;cx<g->size;cx++)
   if(res[cx]>=0){
     c++;
     MARKNODE(cx,marks);
   }
   
  fprintf(ERR,"(found: %d);\n",c);
  
  /* update the best result found */
  if(c>bestsize){
   bestsize=c;
   bestnode=n;
  }
  nodesleft -= c;
 }while(nodesleft>bestsize); /* ..until there cannot be a better result */
 
 fprintf(ERR," <>\n");
 
 /* visit the giant component.. */
 if(bestnode!=n){
  n=bestnode;
  visit(g,res,1,&n,NULL,NULL,NULL,NULL);visits=0;
 }
 
 /* .. and kill the nodes not belonging to it */
 fprintf(ERR," OK. ");
 for(cx=0;cx<g->size;cx++)
  if(res[cx]<0)
    freenode(g,cx);
 free(marks);
}


void il(int nl){
 printf("#Improving LOWER bound: %d; visits: %d.\n",nl,visits);
}
void iu(int nu){
 printf("#Improving UPPER bound: %d; visits: %d.\n",nu,visits);
}
